/*
 * @lc app=leetcode.cn id=1081 lang=typescript
 *
 * [1081] 不同字符的最小子序列
 */

// @lc code=start
function smallestSubsequence(s: string): string {
  // 记录字符出现的次数
  const hash: Map<string, number> = new Map();
  for (const c of s) {
    hash.set(c, (hash.get(c) ?? 0) + 1);
  }

  const m = s.length;
  const stack = [];
  for (const c of s) {
    // 当前字符栈中没有，才进行单调栈操作
    if (!stack.includes(c)) {
      // 当前字符还有剩余才可以出栈
      while (stack.length && c <= stack[stack.length - 1] && hash.get(stack[stack.length - 1])) {
        stack.pop();
      }
      stack.push(c);
    }
    // 将扫描过的字符次数减少1次
    hash.set(c, hash.get(c) - 1);
  }
  // 最后栈中剩下的就是结果
  return stack.join('');
}
// @lc code=end
